package training;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @Author liangzai
 * @Description:
 */
public class J25_5_16_Training {
    //最长相邻不相等子序列 II
    public List<String> getWordsInLongestSubsequence(String[] words, int[] groups) {
        int n = groups.length;
        int[] dp = new int[n];
        int[] pre = new int[n]; // 前缀数组
        int idx = 0;
        Arrays.fill(dp, 1);
        Arrays.fill(pre, -1);
        for(int i=1; i<n; i++){
            for(int j=0; j<i; j++){
                if(groups[i]!=groups[j] && hmDis(words[i], words[j]) && dp[i]<dp[j]+1){
                    dp[i] = dp[j]+1;
                    pre[i] = j;
                }
            }
            idx = dp[i]>dp[idx] ? i : idx;
        }
        List<String> res = new ArrayList<>();
        while(idx != -1){
            res.add(words[idx]);
            idx = pre[idx];
        }
        Collections.reverse(res);
        return res;
    }

    // 求两个字符串之间的hm距离
    public boolean hmDis(String s1, String s2){
        if(s1.length() != s2.length()) return false;
        char[] arr1 = s1.toCharArray();
        char[] arr2 = s2.toCharArray();
        int cnt = 0;
        for(int i=0; i<s1.length(); i++){
            if(arr1[i] != arr2[i]){
                if(cnt++ >= 1) break;
            }
        }
        return cnt==1;
    }
}
